
/** 
 * 字典树的Java实现。实现了插入、查询以及深度优先遍
 * Trie tree's java implementation.(Insert,Search,DFS) 
 * @author RXJ 
 * 
 */ 
public class Trie {
	final int Max_size=26;
	public class TrieNode{
		int nCount;// 记录该字符出现次�?
		char ch; //记录该字�?
		TrieNode[] child;
		public TrieNode(){
			nCount=1;
			child = new TrieNode[Max_size];
		}
	}
	//字典树的插入与构�?
	public void createTrie(TrieNode node ,String str){
		if(str==null || str.length()==0){
			return ;
		}
		char[] leters=str.toCharArray();	//单词转换为一个个字符
		for(int i=0 ;i<leters.length;i++){
			int pos=leters[i]-'a';
			if(node.child[pos]==null){
				node.child[pos]= new TrieNode(); //如果对应的位置的字母为null
			}else{
				node.child[pos].nCount++;   //这个节点字符�?1
			}
			node.ch=leters[i];
			node=node.child[pos]; //重置node为下�?��的node 从�?实现下一个字符的添加
		}
	}
	//字典树的查找
	public int findCount(TrieNode node,String str){
		if(str==null || str.length()==0){
			return -1;
		}
		char[] leters=str.toCharArray();
		for(int i=0 ;i<leters.length;i++){
			int pos = leters[i]-'a';
			if(node.child[pos]==null){
				return 0;
			}else{
				node=node.child[pos]; //到下�?��节点再查�?
			}
		}
		return node.nCount;
	}
	public static void main(String arg[]){
		 String[] strs={     
	                "banana",     
	                "band",     
	                "bee",     
	                "absolute",     
	                "acm",     
	        };     
	        String[] prefix={     
	            "ba",     
	            "b",     
	            "band",     
	            "abc",     
	        };    
	        Trie tree = new Trie();  
	        TrieNode root=tree.new TrieNode();  
	          
	        for (String s : strs) {    
	            tree.createTrie(root, s);    
	        }
	        for(String pre:prefix){     
	            int num=tree.findCount(root,pre);     
	            System.out.println(pre+" "+num);     
	        }  
	}
	
}
